import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.Date;

public class Solver {

	private int[][] tabSudoku = new int[9][9];
	private int[][][] tabPossibility = new int[9][9][10];
	private boolean ended = false;

	public Solver(String fileName) {
		String c;

		try {
			BufferedReader br = new BufferedReader(new FileReader(fileName));
			init();

			int row = 0;
			
			while ((c = br.readLine()) != null) {
				for (int j = 0; j < 9; j++) {
					int value = Integer.parseInt(c.substring(j, j + 1));
					tabSudoku[row][j] = value;
					/*if (value != 0) {
						cleanPossibility(row, j, value);
					}*/
				}
				row++;
			}
			long begin = System.nanoTime();
			//clean possibility grid with initial value
			for (int i = 0; i < 9; i++) {				
				for (int j = 0; j < 9; j++) {
					int valueClean = tabSudoku[i][j];
					if (valueClean != 0) {
						cleanPossibility(i, j, valueClean);
					}
				}
			}
			//solve the grid
			solve();
			if(!ended){
				throw new Exception("unsolvable");
			}
			long end = System.nanoTime();

			System.out.println("execution time(ms) : " + ((double)(end - begin))/1000000);			
			for (int i = 0; i < 9; i++) {
				System.out.println();
				for (int j = 0; j < 9; j++) {
					System.out.print(tabSudoku[i][j] + "|");
				}
			}

		} catch (FileNotFoundException e) {
			System.out.println("File not found");
		} catch (IOException e) {
			System.out.println("Reading error");
		} catch (Exception e) {
			System.out.println(e.getMessage());
			//e.printStackTrace();
		}

	}

	private void solve() throws Exception {
		int[] bestLocation = { 0, 0, 10 };
		//check for spot with least possible choices
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				if (tabSudoku[i][j] == 0
						&& tabPossibility[i][j][0] < bestLocation[2]) {
					bestLocation[0] = i;
					bestLocation[1] = j;
					bestLocation[2] = tabPossibility[i][j][0];
				}
			}
		}
		//if no empty spot(default length) then ended
		if (bestLocation[2] == 10) {
			ended = true;
		} else if (bestLocation[2] < 1) {//if empty spot with no possibility found, unsolvable
			throw new Exception("unsolvable");
		} else {
			boolean possible = false;
			//check every possibility
			for (int k = 1; k < 10; k++) {
				if (tabPossibility[bestLocation[0]][bestLocation[1]][k] == 1) {
					tabSudoku[bestLocation[0]][bestLocation[1]] = k;				
					//remove possibility and check if create impossible spot
					possible = cleanPossibility(bestLocation[0],
							bestLocation[1], k);
					
					if (!possible) {//impossible spot found, backtrack possibility and try next possibility
						tabSudoku[bestLocation[0]][bestLocation[1]] = 0;												
						returnPossibility(bestLocation[0], bestLocation[1],
								k);
					} else {
						//no empty spot, try to solve the current sudoku grid
						solve();
						if (ended) {
							break;
						} else {
							//the current sudoku grid can't be solved, backtrack and try next possibility
							tabSudoku[bestLocation[0]][bestLocation[1]] = 0;							
							returnPossibility(bestLocation[0], bestLocation[1],
									k);
						}
					}
				}
			}
		}
	}

	//remove the possibility that the value in [x,y] can appear in the same row, column or block
	//and check if there is creation of impossible spot
	//return true if possible and false if it create an impossible spot
	private boolean cleanPossibility(int x, int y, int value) {
		boolean possible = true;
		
		for (int i = 0; i < 9; i++) {
			if (i != y) {
				tabPossibility[x][i][value]--;
				if (tabPossibility[x][i][value] == 0) {					
					tabPossibility[x][i][0]--;
					if (tabSudoku[x][i] == 0 && tabPossibility[x][i][0] == 0) {
						possible = false;
					}
				}
			}
		}
		for (int j = 0; j < 9; j++) {
			if (j != x) {
				tabPossibility[j][y][value]--;
				if (tabPossibility[j][y][value] == 0) {					
					tabPossibility[j][y][0]--;
					if (tabSudoku[j][y] == 0 && tabPossibility[j][y][0] == 0) {
						possible = false;
					}
				}
			}
		}
		for (int k = 0; k < 3; k++) {
			for (int l = 0; l < 3; l++) {
				if ((((x / 3) * 3 + k) != x && ((y / 3) * 3 + l) != y)) {
					tabPossibility[(x / 3) * 3 + k][(y / 3) * 3 + l][value]--;
					if (tabPossibility[(x / 3) * 3 + k][(y / 3) * 3 + l][value] == 0) {
						tabPossibility[(x / 3) * 3 + k][(y / 3) * 3 + l][0]--;
						if (tabSudoku[(x / 3) * 3 + k][(y / 3) * 3 + l] == 0
								&& tabPossibility[(x / 3) * 3 + k][(y / 3) * 3
										+ l][0] == 0) {
							possible = false;
						}
					}
				}
			}
		}

		return possible;
	}

	//return the possibility that the value in [x,y] can appear in the same row, column or block
	private void returnPossibility(int x, int y, int value) {

		for (int i = 0; i < 9; i++) {
			if (i != y) {
				if (tabPossibility[x][i][value] != 1) {
					tabPossibility[x][i][value]++;
					if(tabPossibility[x][i][value] == 1){
						tabPossibility[x][i][0]++;
					}					
				}
			}
		}
		for (int j = 0; j < 9; j++) {
			if (j != x) {
				if (tabPossibility[j][y][value] != 1) {
					tabPossibility[j][y][value]++;
					if(tabPossibility[j][y][value] == 1){
						tabPossibility[j][y][0]++;
					}
				}
			}
		}
		for (int k = 0; k < 3; k++) {
			for (int l = 0; l < 3; l++) {
				if ((((x / 3) * 3 + k) != x && ((y / 3) * 3 + l) != y)) {
					if (tabPossibility[(x / 3) * 3 + k][(y / 3) * 3 + l][value] != 1) {
						tabPossibility[(x / 3) * 3 + k][(y / 3) * 3 + l][value]++;
						if(tabPossibility[(x / 3) * 3 + k][(y / 3) * 3 + l][value] == 1){
							tabPossibility[(x / 3) * 3 + k][(y / 3) * 3 + l][0]++;
						}
					}
				}
			}
		}
	}

	//create the initial possibility grid
	private void init() {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				for (int k = 1; k < 10; k++) {
					tabPossibility[i][j][k] = 1;
				}
				tabPossibility[i][j][0] = 9;
			}
		}

	}

}
